package hnsw

import (
	"bytes"
	"compress/gzip"
	"crypto/sha256"
	"encoding/binary"
	"encoding/gob"
	"encoding/hex"
	"errors"
	"fmt"
	"math"
	"sort"
	"strconv"
	"sync"

	// "github.com/klauspost/compress/gzip"
	"encoding/csv"

	"github.com/tendermint/tendermint/my_app/querylayer/vindex/go-hnsw/f32"

	// "io/ioutil"
	"os"
)

type Item interface {
}

// Item the type of the queue
type ItemQueue struct {
	items []Item
}

// /////////               队列
type ItemQueuer interface {
	New() ItemQueue
	Enqueue(t Item)
	Dequeue() *Item
	IsEmpty() bool
	Len() int
}

// New creates a new ItemQueue
func (s *ItemQueue) New() *ItemQueue {
	s.items = []Item{}
	return s
}

func (s *ItemQueue) IsEmpty() bool {
	return len(s.items) == 0
}

// Enqueue adds an Item to the end of the queue
func (s *ItemQueue) Enqueue(t Item) {
	s.items = append(s.items, t)
}

// dequeue
func (s *ItemQueue) Dequeue() *Item {
	if s.IsEmpty() {
		return nil
	}
	item := s.items[0] // 先进先出
	s.items = s.items[1:len(s.items)]

	return &item
}

func (s ItemQueue) Len() int {
	return len(s.items)
}

// 实现sort.Interface接口比较元素方法
func (s ItemQueue) Less(i, j int) bool {
	return s.items[i].(point).distance < s.items[j].(point).distance || (s.items[i].(point).distance == s.items[j].(point).distance && s.items[i].(point).node < s.items[j].(point).node)
}

// 实现sort.Interface接口交换元素方法
func (s ItemQueue) Swap(i, j int) {
	s.items[i], s.items[j] = s.items[j], s.items[i]
}

// 调整元素
func (s *ItemQueue) Alter(nodeID int, dist float32) {
	for i := 0; i < s.Len(); i++ {
		if s.items[i].(point).node == nodeID {
			if s.items[i].(point).distance < dist {
				s.items[i] = point{nodeID, dist}
			}
			return
		}
	}
	// fmt.Println(nodeID,dist)
	s.Enqueue(point{nodeID, dist})
}

// /////////////////        栈
type ItemStack struct {
	items []Item
}

func (s *ItemStack) New() *ItemStack {
	s.items = []Item{}
	return s
}

func (s *ItemStack) Push(t Item) {
	s.items = append(s.items, t)
}

func (s *ItemStack) Pop() *Item {
	item := s.items[len(s.items)-1] // 后进先出
	s.items = s.items[0 : len(s.items)-1]
	return &item

}

// 记录叶节点中MHT的叶节点的指针
//var

// MHTree节点
type TreeNode struct {
	left     *TreeNode
	right    *TreeNode
	parent   *TreeNode
	digest   []byte
	flag     bool
	findNode *node
	p        string
	gridsize Point
}

type VO struct {
	value string
}

type point struct {
	node     int
	distance float32
}

func PointToBytes(data Point) []byte {
	var byteData []byte

	for _, value := range data {
		bytes := make([]byte, 4)
		binary.LittleEndian.PutUint32(bytes, math.Float32bits(float32(value)))
		byteData = append(byteData, bytes...)
	}
	return byteData
}

func BytesToPoint(data []byte) Point {
	var row Point

	for j := 0; j < len(data); j += 4 {
		value := math.Float32frombits(binary.LittleEndian.Uint32(data[j : j+4]))
		row = append(row, float32(value))
	}
	return row
}

func IntToBytes(data []int8) []byte {
	var byteData []byte

	for _, value := range data {
		byteData = append(byteData, byte(value))
	}
	return byteData
}

func BytesToInt(data []byte) []int8 {
	row := make([]int8, len(data))

	for i, b := range data {
		row[i] = int8(b)
	}
	return row
}

// 将hash值直接映射为string
func bytetostring(hash []byte) string {
	return hex.EncodeToString(hash)
	// return string(hash)
}

// 将string转为hash值
func stringtobyte(hash string) []byte {
	result, _ := hex.DecodeString(hash)
	return result
}

// 计算更新的层数
func countlevel(n int) (int, int, int) {
	//计算MHT有几层
	level := 0
	for math.Pow(2, float64(level)) < float64(n) {
		level++
	}
	//计算应该在哪加
	count := 0
	for n > 0 && n%2 == 0 {
		n /= 2
		count++
	}
	return n, count, level - count
}

func gethash(str string) []byte {
	value_hash := sha256.New()
	value_hash.Write([]byte(str))
	return value_hash.Sum(nil)
}

func findnode(node int, Q ItemQueue, is_result bool) bool {
	for i := 0; i < Q.Len(); i++ {
		if is_result && node == Q.items[i].(point).node {
			return true
		} else if !is_result && node == Q.items[i].(int) {
			return true
		}
	}
	return false
}

func (h *Hnsw) PrintADS(ADS []*TreeNode, truthADS *TreeNode) {
	var vosize int
	for level := 0; level < len(ADS); level++ {
		// fmt.Printf("%x\n",ADS[level].digest)
		high := 1
		leaf := h.ADS[level]
		for leaf.left != nil {
			high++
			leaf = leaf.left
		}
		vosize += int((math.Pow(2.0, float64(high)) - 1) * 64)
	}
	high := 1
	leaf := truthADS
	for leaf.left != nil {
		high++
		leaf = leaf.left
	}
	vosize += int((math.Pow(2.0, float64(high)) - 1) * 64)
	fmt.Printf("ADSsize:%d bytes\n", vosize)
}

func (h *Hnsw) PrintVOsize(VOq, truth_VO []byte, point_info map[int]([]int8), true_point_info []byte, grid_info []([]byte)) int {
	var vosize int
	// for i := 0; i < VOq.Len(); i++ {
	// 	// if i > 0 {fmt.Println(VOq.items[i].(VO).value)}
	// 	vosize += len(VOq.items[i].(VO).value)
	// }
	vosize += len(VOq)
	fmt.Printf("MHTVO_size:%d bytes\n", vosize)
	// fmt.Printf("MHTVO[0]_size:%d bytes\n",len(VOq.items[VOq.Len()-1].(VO).value))
	vosize += len(truth_VO)
	fmt.Printf("truthMHTVO_size:%d bytes\n", len(truth_VO))
	for _, v := range point_info {
		vosize += len(v)
	}
	fmt.Printf("int8_size:%d bytes\n", len(point_info)*128)
	// for _,v := range true_point_info{
	// 	vosize += len(v)*4
	// }
	vosize += len(true_point_info)
	fmt.Printf("float32_size:%d bytes\n", len(true_point_info))
	// for _,grid := range grid_info{
	// 	// for _,v := range grid{
	// 	// 	vosize += len(v)*4
	// 	// }
	// 	vosize += len(grid)
	// }
	// fmt.Printf("float32_size:%d bytes\n",len(grid_info)*512)
	// fmt.Printf("VOsize:%d bytes\n",vosize)
	return vosize
}

func (h *Hnsw) GetADS() (*TreeNode, []*TreeNode) {
	return h.TruthADS, h.ADS
}

// 构建ADS
func (h *Hnsw) BuildADS() {
	//真实位置的ADS
	var wg sync.WaitGroup // 用于等待所有goroutine完成
	nodeSlice := make([]*TreeNode, len(h.nodes))
	for id := 0; id < len(h.nodes); id++ {
		wg.Add(1) // 在启动goroutine之前增加等待计数
		go func(id int) {
			defer wg.Done() // 在goroutine完成时减少等待计数
			// str := tostring(h.nodes[id].p)
			str := string(PointToBytes(h.nodes[id].p))
			Node := new(TreeNode)
			Node.left = nil
			Node.right = nil
			Node.digest = gethash(str)
			Node.flag = false
			Node.findNode = &(h.nodes[id])
			Node.p = strconv.Itoa(id)
			h.nodes[id].findpoint = Node
			// result.Enqueue(Node)
			nodeSlice[id] = Node
		}(id)
	}
	wg.Wait()

	h.TruthADS = buildMHT(nodeSlice)
	//相对位置的ADS
	epID := h.enterpoint
	currentMaxLayer := h.nodes[epID].level

	h.ADS = make([]*TreeNode, currentMaxLayer+1)

	for level := currentMaxLayer; level >= 0; level-- {
		h.ADS[level] = h.BuildHnswADS(level)
	}
}

func (h *Hnsw) BuildHnswADS(level int) *TreeNode {
	tempSlice := make([]*TreeNode, 0)
	for id := 0; id < len(h.nodes); id++ {
		if h.nodes[id].level < level {
			continue
		}
		nodeSlice, str, gridsize := h.BuildEmMHT(uint32(id), level)

		Node := new(TreeNode)
		Node.left = nil
		Node.right = nodeSlice
		Node.digest = gethash(str)
		Node.flag = false
		Node.findNode = &(h.nodes[id])
		Node.p = strconv.Itoa(id)
		Node.gridsize = gridsize
		h.nodes[id].findleaf[level] = Node
		tempSlice = append(tempSlice, Node) //(Node)
	}
	return buildMHT(tempSlice)
}

// 自下而上计算merkle root
func buildMHT(nodeSlice []*TreeNode) *TreeNode {
	var wg sync.WaitGroup
	for len(nodeSlice) > 1 {
		pairCount := len(nodeSlice)/2 + len(nodeSlice)%2
		nextSlice := make([]*TreeNode, pairCount) // 为下一轮合并准备的新切片

		// 并行合并节点
		for i := 0; i < pairCount; i++ {
			wg.Add(1)
			go func(i int) {
				defer wg.Done()
				l := nodeSlice[2*i]
				var r *TreeNode
				if (2*i + 1) >= len(nodeSlice) {
					r = l
				} else {
					r = nodeSlice[2*i+1]
				}
				Node := new(TreeNode)
				Node.left = l
				Node.right = r
				Node.digest = gethash(string(l.digest) + string(r.digest))
				Node.flag = false

				l.parent = Node
				r.parent = Node
				nextSlice[i] = Node // 将新节点添加到下一轮的切片中
			}(i)
		}
		wg.Wait()             // 等待本轮所有合并操作完成
		nodeSlice = nextSlice // 为下一轮迭代更新切片
	}
	return nodeSlice[0]
}

// 叶节点的MHT
func (h *Hnsw) BuildEmMHT(id uint32, level int) (*TreeNode, string, []float32) {
	var wg sync.WaitGroup
	var candidates []Point
	str := string(PointToBytes(h.nodes[id].p))
	friends := h.getFriends(id, level)
	for _, i := range friends {

		candidates = append(candidates, h.nodes[i].p)
		str += "," + strconv.Itoa(int(i))
	}
	grids, gridsize := Useint(candidates, h.nodes[id].p)
	str += "*"
	//如果相对位置没有存，那么网格大小信息也不需要发送
	substr := string(PointToBytes(gridsize))
	nodeSlice := make([]*TreeNode, len(grids))
	if len(nodeSlice) == 0 {
		str += bytetostring(gethash(substr))
		return nil, str, gridsize
	}
	for i := range grids {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			substr := string(IntToBytes(grids[i]))
			Node := new(TreeNode)
			Node.left = nil
			Node.right = nil
			Node.digest = gethash(substr)
			Node.flag = false
			Node.p = strconv.Itoa(int(friends[i]))
			key := strconv.FormatUint(uint64(level), 10) + "-" + strconv.FormatUint(uint64(id), 10) + "-" + strconv.FormatUint(uint64(friends[i]), 10)
			h.loca_point.Store(key, Node)
			nodeSlice[i] = Node
		}(i)
	}
	wg.Wait()
	root := buildMHT(nodeSlice)

	substr += "," + bytetostring(root.digest)
	str += bytetostring(gethash(substr))
	return root, str, gridsize
}

// 更新MHT
func (h *Hnsw) MHT_Add(mht *TreeNode, newid uint32, count int, pathlen int, selflevel int, adstype int, level int) *TreeNode {
	//自计算
	nodeSlice := make([]*TreeNode, int(math.Pow(2, float64(selflevel))))
	Node := new(TreeNode)
	var str string
	if adstype == 0 {
		str = string(PointToBytes(h.nodes[newid].p))
		Node.right = nil
	} else {
		nodeSlice, substr, gridsize := h.BuildEmMHT(newid, level)
		Node.right = nodeSlice
		Node.gridsize = gridsize
		str = substr
	}
	Node.left = nil
	Node.digest = gethash(str)
	Node.flag = false
	Node.findNode = &(h.nodes[newid])
	Node.p = strconv.Itoa(int(newid))
	if adstype == 0 {
		h.nodes[newid].findpoint = Node
	} else {
		h.nodes[newid].findleaf[level] = Node
	}
	nodeSlice[0] = Node
	for i := 1; i < len(nodeSlice); i++ {
		nodeSlice[i] = Node
	}
	overNode := buildMHT(nodeSlice)
	if count == 1 {
		Node := new(TreeNode)
		Node.left = mht
		Node.right = overNode
		Node.digest = gethash(string(mht.digest) + string(overNode.digest))
		Node.flag = false

		mht.parent = Node
		overNode.parent = Node
		// if adstype != 0 {
		// 	testNode := Node
		// 	for testNode.left != nil {
		// 		testNode = testNode.right
		// 	}
		// 	fmt.Println("add:", testNode.findNode.findleaf)
		// }
		return Node
	}
	//找到添加的路径
	path := make([]bool, 32)
	for i := 0; i < 32; i++ {
		mask := 1 << i
		// 使用与操作检查num的第i位
		if count&mask != 0 {
			path[i] = true
		} else {
			path[i] = false
		}
	}
	// if len(h.nodes) < 500 {
	// fmt.Println(len(h.nodes)-1, count, newid, path[:pathlen])
	// }
	nowNode := mht
	for i := pathlen - 1; i > 0; i-- {
		// fmt.Printf("%d before: %x\n", newid, nowNode.digest)
		if path[i] {
			nowNode = nowNode.right
		} else {
			nowNode = nowNode.left
		}
	}
	// fmt.Printf("left: %x\n", nowNode.left.digest)
	nowNode.right = overNode
	nowNode.digest = gethash(string(nowNode.left.digest) + string(overNode.digest))
	// fmt.Printf("%x\n", nowNode.digest)
	overNode.parent = nowNode
	nowNode.left.parent = nowNode
	//沿路返回重新计算
	for i := 1; i < pathlen; i++ {
		nowNode = nowNode.parent
		if path[i] {
			nowNode.digest = gethash(string(nowNode.left.digest) + string(nowNode.right.digest))
		} else {
			nowNode.right = nowNode.left
			nowNode.digest = gethash(string(nowNode.left.digest) + string(nowNode.right.digest))
		}
	}
	// if adstype != 0 {
	// 	testNode := nowNode
	// 	for testNode.left != nil {
	// 		testNode = testNode.right
	// 	}
	// 	fmt.Println("add:", testNode.findNode.findleaf)
	// }
	return nowNode
}

// 更新MHT
func (h *Hnsw) MHT_Update(first uint32, level int) {
	if level >= len(h.nodes[first].findleaf) {
		return
	}
	// if level == 0 && first > 2 {
	// 	fmt.Printf("update before %d:%x\n", first, h.nodes[first].findleaf[level].parent.digest)
	// }
	Node := h.nodes[first].findleaf[level]
	nodeSlice, str, gridsize := h.BuildEmMHT(first, level)
	Node.right = nodeSlice
	Node.gridsize = gridsize
	Node.digest = gethash(str)

	for Node.parent != nil {
		Node.parent.digest = gethash(string(Node.parent.left.digest) + string(Node.parent.right.digest))
		Node = Node.parent
	}
	// if level == 0 && first > 2 {
	// 	fmt.Printf("update %d:%x\n", first, h.nodes[first].findleaf[level].parent.digest)
	// }
}

// 更新ADS
func (h *Hnsw) UpdateADS(newID uint32) {

	//更新truthADS
	n, selflevel, pathlen := countlevel(h.levCount[0])
	h.TruthADS = h.MHT_Add(h.TruthADS, newID, n, pathlen, selflevel, 0, 0)

	currentMaxLayer := h.maxLayer
	curlevel := h.nodes[newID].level
	// fmt.Println("now:", newID, "maxlevel:", max(curlevel, currentMaxLayer))
	//新的层数
	if curlevel > currentMaxLayer {
		newADS := make([]*TreeNode, 0)
		newADS = append(newADS, h.ADS...)

		for level := currentMaxLayer + 1; level < curlevel+1; level++ {
			newADS = append(newADS, h.BuildHnswADS(level))
		}
		h.ADS = newADS
	}
	//更新每层的ADS
	for level := min(curlevel, currentMaxLayer); level >= 0; level-- {
		n, selflevel, pathlen = countlevel(h.levCount[level])
		h.ADS[level] = h.MHT_Add(h.ADS[level], newID, n, pathlen, selflevel, 1, level)
	}
}

// 构建VO
func (h *Hnsw) getVO(root *TreeNode, level int) string {
	type StackItem struct {
		Node     *TreeNode
		State    int
		LeftStr  string
		RightStr string
	}

	stack := []*StackItem{{Node: root, State: 0}}
	var result string

	for len(stack) > 0 {
		top := stack[len(stack)-1]
		current := top.Node

		switch top.State {
		case 0: // 初始状态，处理当前节点
			if !current.flag {
				result = bytetostring(current.digest)
				stack = stack[:len(stack)-1] // Pop
			} else if current.left != nil {
				current.flag = false
				top.State = 1                                         // 更新状态为处理左子树
				stack = append(stack, &StackItem{Node: current.left}) // 将左子树压栈
			} else {
				current.flag = false
				str := "["
				str += current.p

				// substr := tostring(current.gridsize)
				substr := string(PointToBytes(current.gridsize))

				v := current.findNode
				if len(v.friends) > level {
					for _, next := range v.friends[level] {
						str += "," + strconv.Itoa(int(next))
					}
				}
				// if level == 0 {
				// 	fmt.Println(current.right.digest)
				// }
				str += "*"
				if current.right != nil {
					if current.right.flag {
						substr = "*" + current.p + "," + h.gettruthVO(current.right) + "*"
						str += substr
					} else {
						substr += "," + h.gettruthVO(current.right)
						str += bytetostring(gethash(substr))
					}
				} else {
					str += bytetostring(gethash(substr))
				}

				str += "]"

				result = str
				stack = stack[:len(stack)-1] // Pop
			}

		case 1: // 完成左子树处理，处理右子树
			top.LeftStr = result
			top.State = 2
			stack = append(stack, &StackItem{Node: current.right})

		case 2: // 完成右子树处理
			top.RightStr = result
			result = "{" + top.LeftStr + "," + top.RightStr + "}"
			stack = stack[:len(stack)-1]
		}
	}
	return result
}

func (h *Hnsw) gettruthVO(root *TreeNode) string {
	type StackItem struct {
		Node     *TreeNode
		State    int
		LeftStr  string
		RightStr string
	}

	stack := []*StackItem{{Node: root, State: 0}}
	var result string

	for len(stack) > 0 {
		top := stack[len(stack)-1]
		current := top.Node

		switch top.State {
		case 0: // 初始状态，处理当前节点
			if !current.flag {
				result = bytetostring(current.digest)
				stack = stack[:len(stack)-1] // Pop
			} else if current.left != nil {
				current.flag = false
				top.State = 1                                         // 更新状态为处理左子树
				stack = append(stack, &StackItem{Node: current.left}) // 将左子树压栈
			} else {
				current.flag = false
				str := "["
				str += current.p
				str += "]"
				result = str
				stack = stack[:len(stack)-1] // Pop
			}

		case 1: // 完成左子树处理，处理右子树
			top.LeftStr = result
			top.State = 2
			stack = append(stack, &StackItem{Node: current.right})

		case 2: // 完成右子树处理
			top.RightStr = result
			result = "{" + top.LeftStr + "," + top.RightStr + "}"
			stack = stack[:len(stack)-1]
		}
	}

	return result
}

func (h *Hnsw) Verify(truth_VO string, true_point_info map[int]Point, truthADS *TreeNode) error {
	vo := truth_VO
	var stack ItemStack
	stack.New()
	var i int
	// fmt.Println(truth_VO)
	for i = 0; i < len(vo); i++ {
		if vo[i] == '[' {
			head := i + 1
			for ; vo[i] != ']'; i++ {
			}

			vo_id, _ := strconv.Atoi(vo[head:i])
			if _, ok := true_point_info[vo_id]; !ok {
				return errors.New("真实点未找到")
			}
			// str := tostring(true_point_info[vo_id])
			str := string(PointToBytes(true_point_info[vo_id]))
			//重构vo
			newvo := vo[0 : head-1]
			newvo += bytetostring(gethash(str))
			newi := len(newvo)
			newvo += vo[i+1:]
			vo = newvo
			i = newi
		}
	}
	// fmt.Println(vo)
	for i = 0; i < len(vo); i++ {
		if vo[i] == '}' {
			r := (*stack.Pop()).([]byte)
			l := (*stack.Pop()).([]byte)
			// fmt.Printf("%x*%x\n",l,r)
			stack.Push(gethash(string(l) + string(r)))
		} else if vo[i] != '{' && vo[i] != ',' {
			head := i
			for ; i < len(vo) && vo[i] != '}' && vo[i] != ','; i++ {
			}
			// fmt.Println(vo[head:i])
			hash := stringtobyte(vo[head:i])
			stack.Push(hash)
			if i < len(vo) && vo[i] == '}' {
				i--
			}
		}
	}
	if !bytes.Equal(truthADS.digest, (*stack.Pop()).([]byte)) {
		fmt.Println("验证失败了")
		return errors.New("验证失败了")
	}
	return nil
}

func Verify_grid(grid_VO string, point_info map[int][]int8) ([]byte, map[int][]int8) {
	vo := grid_VO
	var stack ItemStack
	stack.New()
	var i int
	// fmt.Println("grid:"+vo)
	candidates := make(map[int]([]int8))
	for i = 0; i < len(vo); i++ {
		if vo[i] == '[' {
			head := i + 1
			for ; vo[i] != ']'; i++ {
			}
			vo_id, _ := strconv.Atoi(vo[head:i])
			if _, ok := point_info[vo_id]; !ok {
				// fmt.Println("grid:"+vo)
				fmt.Println("没有找到点")
				return nil, candidates
			}

			candidates[vo_id] = point_info[vo_id]
			// str := inttostring(point_info[vo_id])
			str := string(IntToBytes(point_info[vo_id]))
			//重构vo
			newvo := vo[0 : head-1]
			newvo += bytetostring(gethash(str))
			newi := len(newvo)
			newvo += vo[i+1:]
			vo = newvo
			i = newi
		}
	}
	// fmt.Println(vo)
	for i = 0; i < len(vo); i++ {
		if vo[i] == '}' {
			r := (*stack.Pop()).([]byte)
			l := (*stack.Pop()).([]byte)
			// fmt.Printf("%x*%x\n",l,r)
			stack.Push(gethash(string(l) + string(r)))
		} else if vo[i] != '{' && vo[i] != ',' {
			head := i
			for ; i < len(vo) && vo[i] != '}' && vo[i] != ','; i++ {
			}
			// fmt.Println(vo[head:i])
			hash := stringtobyte(vo[head:i])
			stack.Push(hash)
			if i < len(vo) && vo[i] == '}' {
				i--
			}
		}
	}
	return (*stack.Pop()).([]byte), candidates
}

func (h *Hnsw) Verify_bound(q Point, VO_queue *ItemQueue, point_info map[int][]int8, true_point_info map[int]Point, grid_info []map[int]Point) (error, map[int]float32) {
	// copy_VO_queue := VO_queue
	vo := (*VO_queue.Dequeue()).(VO).value
	// var stack ItemStack
	var bound_num int
	bound_info := make(map[int]float32)
	for level := len(grid_info) - 1; level >= 0; level-- {
		var i int
		// fmt.Println(level,vo)
		// if level == len(grid_info)-2 {fmt.Println(level,vo)}
		for i = 0; i < len(vo); i++ {
			if vo[i] == '*' && vo[i+1] == '*' {
				//获取中心点坐标
				c_head := i
				for ; vo[c_head] != '['; c_head-- {
				}
				c_tail := c_head
				for ; vo[c_tail] != ',' && vo[c_tail] != '*'; c_tail++ {
				}
				center, _ := strconv.Atoi(vo[c_head+1 : c_tail])
				nowpoint := true_point_info[center]

				//获取网格大小并计算网格半径
				head := i + 2
				for ; vo[i] != ','; i++ {
				}

				grid_id, _ := strconv.Atoi(vo[head:i])
				if _, ok := grid_info[level][grid_id]; !ok {
					fmt.Println(vo[head:i])
					fmt.Println("找不到网格大小")
					return nil, bound_info
				}
				gridsize := grid_info[level][grid_id]
				// str := tostring(gridsize) + ","
				str := string(PointToBytes(gridsize)) + ","

				//验证相对位置并计算点的距离下界
				g_head := i + 1
				for ; vo[i] != '*'; i++ {
				}
				digest, grids := Verify_grid(vo[g_head:i], point_info)
				if level == 0 {
					bound_num += len(grids)
				}
				str += bytetostring(digest)
				for id, grid := range grids {

					gridmin := make([]float32, len(nowpoint))
					gridmax := make([]float32, len(nowpoint))
					for i := 0; i < len(nowpoint); i++ {
						gridmin[i] = nowpoint[i] + float32(grid[i])*gridsize[i]
						gridmax[i] = nowpoint[i] + float32(grid[i])*gridsize[i] + gridsize[i]
					}
					dist := cal_grid_distance(gridmin, gridmax, q)

					bound_info[id] = dist
				}
				//重构vo
				newvo := vo[0 : head-1]
				newvo += bytetostring(gethash(str))
				newi := len(newvo)
				newvo += vo[i+1:]
				vo = newvo
				i = newi
			}
		}
		// fmt.Println(vo)
		if level > 0 {
			VO_queue.Enqueue(VO{value: vo})
			vo = (*VO_queue.Dequeue()).(VO).value
		} else {
			// fmt.Printf("MHTVO[0]_size:%d bytes\n",vo)
		}
	}
	// fmt.Printf("bound_num:%d\n",bound_num)
	VO_queue.Enqueue(VO{value: vo})
	return nil, bound_info
}

func (h *Hnsw) Rebuild(q Point, VO_begin int, VO_queue ItemQueue, ef int, ADS []*TreeNode, true_point_info map[int]Point, bound_info map[int]float32) error {

	vo := (*VO_queue.Dequeue()).(VO).value
	// fmt.Println(vo)
	begin := VO_begin
	var tempbegin ItemQueue
	tempbegin.New()

	var result ItemQueue
	result.New()

	cal_distance := f32.L2Squared8AVX
	// fmt.Println(VO_queue.Len())
	var stack ItemStack
	for level := len(ADS) - 1; level >= 0; level-- {
		stack.New()
		var i int
		// if level == len(ADS)-3 {fmt.Println(level,vo)}
		// fmt.Println(level,vo)
		for {
			for i = 0; i < len(vo); i++ {
				if vo[i] == '[' {
					//读取中心点的真实数据
					head := i + 1
					for ; vo[i] != ',' && vo[i] != '*'; i++ {
					}
					// fmt.Println(vo[head:i])
					// hash,_ := stringtobyte(vo[head:i])
					var str string

					nowpoint := true_point_info[begin]
					vo_id, _ := strconv.Atoi(vo[head:i])
					// if level ==0{fmt.Println(begin)}
					// fmt.Println(begin)
					if begin == vo_id {
						// str += tostring(nowpoint)
						str += string(PointToBytes(nowpoint))
					} else {
						// fmt.Println(begin)
						continue
					}
					if !findnode(begin, result, true) {
						// fmt.Println(begin)
						result.Enqueue(point{begin, cal_distance(nowpoint, q)})
						// fmt.Println(tostring(node.location))
					}
					//读取相对位置的下界
					for vo[i] != '*' {
						friend_head := i + 1
						for i = i + 1; vo[i] != ',' && vo[i] != '*'; i++ {
						}
						// fmt.Println(vo[friend_head:i])
						friend, _ := strconv.Atoi(vo[friend_head:i])
						str += "," + vo[friend_head:i]
						if _, ok := true_point_info[friend]; !ok {
							//真实位置没有，用相对位置的下界代替
							dist := bound_info[friend]
							// fmt.Println(friend,dist)
							(&result).Alter(friend, dist*dist)
						} else {
							//通过真实位置计算出相对位置
							friend_info := true_point_info[friend]
							(&result).Alter(friend, cal_distance(friend_info, q))
						}
					}
					g_head := i + 1
					for ; vo[i] != ']'; i++ {
					}
					str += "*" + vo[g_head:i]
					// fmt.Println(str)

					// if level == 0{
					// 	fmt.Println(begin)
					// 	for k := 0;k <= ef*2 && k < result.Len();k++ {
					// 		fmt.Println(result.items[k].(point))
					// 	}
					// }
					//重构vo
					newvo := vo[0 : head-1]
					newvo += bytetostring(gethash(str))
					newvo += vo[i+1:]
					vo = newvo
					break
				}
			}
			// fmt.Println(begin,vo)
			if i == len(vo) {
				fmt.Println(level, begin, vo)
				// fmt.Printf("--------%x\n",hash)
				// for k := 0;k < begin.Len();k++ {
				// 	fmt.Println(tostring(begin.items[k].(Point)))
				// }
				for k := 0; k <= ef*2 && k < result.Len(); k++ {
					fmt.Println(result.items[k].(point))
				}
				fmt.Println("找不到下一次迭代点")
				// fmt.Scan(&vo)
				return errors.New("验证失败")
			}

			//计算下一起点
			sort.Sort(result)
			// if level == 0{
			// 	for k := 0;k < result.Len();k++ {
			// 		fmt.Println(result.items[k].(point))
			// 	}
			// }
			// fmt.Println(result.items[0].(point))
			// sorttime += float64(time.Since(start).Seconds())
			// fmt.Printf("__")
			if level != 0 {
				if !result.IsEmpty() && result.items[0].(point).node != begin {
					// fmt.Println(666)
					begin = result.items[0].(point).node
					result.New()
				} else {
					// fmt.Println(666)
					if level == 1 {
						tempbegin.Enqueue(begin)
					}
					result.New()
					break
				}
			} else {
				// mi := min(ef,result.Len())
				// for j:= 0; j< mi;j++{
				// 	fmt.Println(result.items[j].(point).distance)
				// }

				for i = 0; i < min(ef, len(result.items)); i++ {
					if !findnode(result.items[i].(point).node, tempbegin, false) {
						// fmt.Println(result.items[i].(point).node)
						// fmt.Println(begin)
						begin = result.items[i].(point).node
						tempbegin.Enqueue(result.items[i].(point).node)
						break
					}
				}
				if i == min(ef, len(result.items)) {
					break
				}
			}
		}
		// if level == 0 {
		// 	fmt.Println(vo)
		// }
		// fmt.Println(vo)
		for i = 0; i < len(vo); i++ {
			if vo[i] == '}' {
				r := (*stack.Pop()).([]byte)
				l := (*stack.Pop()).([]byte)
				// fmt.Printf("%x*%x\n",l,r)
				stack.Push(gethash(string(l) + string(r)))
			} else if vo[i] != '{' && vo[i] != ',' {
				head := i
				for ; i < len(vo) && vo[i] != '}' && vo[i] != ','; i++ {
				}
				// fmt.Println(vo[head:i])
				hash := stringtobyte(vo[head:i])
				stack.Push(hash)
				if i < len(vo) && vo[i] == '}' {
					i--
				}
			}
		}
		// fmt.Printf("%d:%x+%x\n", level, ADS[level].digest, (stack.items[0].([]byte)))

		if !bytes.Equal(ADS[level].digest, (*stack.Pop()).([]byte)) {
			fmt.Println("验证失败了", level)
			return errors.New("验证失败了")
		}
		if !VO_queue.IsEmpty() {
			vo = (*VO_queue.Dequeue()).(VO).value
		}
	}
	return nil
}

func Useint(candidates []Point, center Point) ([][]int8, []float32) {
	d := len(center)
	//计算网格大小
	maxlist := make([]float32, d)
	for i := 0; i < d; i++ {
		maxlist[i] = 1.1
	}
	// fmt.Println(gridR)
	//计算相对位置
	grid := make([][]int8, len(candidates))
	for j := 0; j < len(grid); j++ {
		grid[j] = make([]int8, d)
		for i := 0; i < d; i++ {
			grid[j][i] = int8(math.Floor(float64((candidates[j][i] - center[i]) / maxlist[i])))
		}
		// fmt.Println(grid[j])
	}
	return grid, maxlist
}

var variances []float32
var ps []float64

func truthID(candidates []Point, center, query Point, mindist float32, minID uint32, pid []uint32) ([][]int8, []uint32, []float32) {
	d := len(center)
	grid, maxlist := Useint(candidates, center)
	// var gridR float32
	// for _,item := range maxlist{
	// 	gridR += item*item
	// }
	// gridR = float32(math.Sqrt(float64(gridR)))
	//选择部分维度

	//计算所有相对位置的上下界
	// var minbound float32 = float32(math.Sqrt(float64(mindist)))
	var minmaxbound float32 = float32(math.Sqrt(float64(mindist)))
	var wg sync.WaitGroup
	bounds := make([]float32, len(candidates))
	for j := 0; j < len(bounds); j++ {
		wg.Add(1)
		go func(j int) {
			defer wg.Done()
			gridmin := make([]float32, d)
			gridmax := make([]float32, d)
			for i := 0; i < d; i++ {
				gridmin[i] = center[i] + float32(grid[j][i])*maxlist[i]
				gridmax[i] = center[i] + float32(grid[j][i])*maxlist[i] + maxlist[i]
			}

			dist := cal_grid_distance(gridmin, gridmax, query)
			bounds[j] = dist
		}(j)
	}
	wg.Wait()

	//计算范围：从最近点的下界开始查找，如果有下界小于最近的上界，则需要发送的点数+1
	var result []uint32
	for i, bound := range bounds {
		if bound < minmaxbound && uint32(i) != minID {
			result = append(result, pid[i])
			// bounds[i] = float32(math.Sqrt(float64(f32.L2Squared8AVX(candidates[i],query))))
		}
	}
	// fmt.Println(minbound,minmaxbound)

	return grid, result, bounds
}

func Getcsv(flag bool) {
	// 创建一个CSV文件
	var path string
	if flag {
		path = "C:/Users/99692/Desktop/python/variance.csv"
	} else {
		path = "C:/Users/99692/Desktop/python/ps.csv"
	}
	file, err := os.Create(path)
	if err != nil {
		panic(err)
	}
	defer file.Close()

	writer := csv.NewWriter(file)
	defer writer.Flush()

	// 写入数据
	if flag {
		for _, value := range variances {
			err := writer.Write([]string{strconv.FormatFloat(float64(value), 'f', 10, 32)})
			if err != nil {
				panic(err)
			}
		}
	} else {
		for _, value := range ps {
			err := writer.Write([]string{strconv.FormatFloat(value, 'f', 10, 64)})
			if err != nil {
				panic(err)
			}
		}
	}
}

// 计算点和长方体的距离
func cal_grid_distance(minCoords, maxCoords, q Point) float32 {
	var distanceSquared float32

	for i := 0; i < len(minCoords); i++ {
		var d float32
		if q[i] < minCoords[i] {
			d = minCoords[i] - q[i]
		} else if q[i] > maxCoords[i] {
			d = q[i] - maxCoords[i]
		}
		distanceSquared += d * d
	}

	return float32(math.Sqrt(float64(distanceSquared)))
}

// 压缩数据
func compress(data []byte) ([]byte, error) {
	var gzipBuf bytes.Buffer
	gzipWriter := gzip.NewWriter(&gzipBuf)
	_, err := gzipWriter.Write(data)
	gzipWriter.Close()
	gzipCompressed := gzipBuf.Bytes()
	return gzipCompressed, err
}

// 解压缩数据
func decompress(data []byte) ([]byte, error) {
	gzipReader, _ := gzip.NewReader(bytes.NewBuffer(data))
	var gzipDecompressedBuf bytes.Buffer
	_, err := gzipDecompressedBuf.ReadFrom(gzipReader)
	gzipReader.Close()
	gzipDecompressed := gzipDecompressedBuf.Bytes()
	return gzipDecompressed, err
}

func (h *Hnsw) Compress_all(VO_queue []string, truth_VO string, true_point_info map[int]Point, grid_info [](map[int]Point)) ([]byte, []byte, []byte, []([]byte)) {
	//压缩VO_queue
	var VO_queue_json []byte
	var vo_buf bytes.Buffer
	vo_encoder := gob.NewEncoder(&vo_buf)
	vo_encoder.Encode(VO_queue)
	VO_queue_json, _ = compress(vo_buf.Bytes())
	//压缩truth_VO
	truth_VO_json, _ := compress([]byte(truth_VO))
	//压缩true_point_info
	var true_point_info_json []byte
	var buf bytes.Buffer
	encoder := gob.NewEncoder(&buf)
	encoder.Encode(true_point_info)
	true_point_info_json, _ = compress(buf.Bytes())
	//压缩grid_info
	grid_info_json := make([]([]byte), len(grid_info))
	for i, _ := range grid_info_json {
		var buf bytes.Buffer
		encoder := gob.NewEncoder(&buf)
		encoder.Encode(grid_info[i])
		grid_info_json[i], _ = compress(buf.Bytes())
	}
	return VO_queue_json, truth_VO_json, true_point_info_json, grid_info_json
}

func (h *Hnsw) Decompress_all(VO_queue_json, truth_VO_json, true_point_info_json []byte, grid_info_json []([]byte)) (ItemQueue, string, map[int]Point, [](map[int]Point)) {
	var VO_queue ItemQueue
	VO_queue.New()
	var vo_temp []string
	decompressedData, _ := decompress(VO_queue_json)
	buf := bytes.NewBuffer(decompressedData)
	gob.NewDecoder(buf).Decode(&vo_temp)
	for level := len(grid_info_json) - 1; level >= 0; level-- {
		VO_queue.Enqueue(VO{value: vo_temp[level]})
	}

	var truth_VO string
	decompressedData, _ = decompress(truth_VO_json)
	truth_VO = string(decompressedData)

	true_point_info := make(map[int]Point)
	decompressedData, _ = decompress(true_point_info_json)
	// json.Unmarshal(decompressedData, &true_point_info)
	buf = bytes.NewBuffer(decompressedData)
	gob.NewDecoder(buf).Decode(&true_point_info)

	grid_info := make([]map[int]Point, len(grid_info_json))
	for i := 0; i < len(grid_info_json); i++ {
		grid_info[i] = make(map[int]Point)
		decompressedData, _ = decompress(grid_info_json[i])
		// json.Unmarshal(decompressedData, &grid_info[i])
		buf := bytes.NewBuffer(decompressedData)
		gob.NewDecoder(buf).Decode(&grid_info[i])
	}
	return VO_queue, truth_VO, true_point_info, grid_info
}

func (h *Hnsw) verification(enterpoint int, vo_temp []string, truth_VO string, point_info map[int]([]int8), true_point_info map[int]Point, grid_info []map[int]Point, truthADS *TreeNode, ADS []*TreeNode, query Point, efSearch int) error {

	VO_queue_json, truth_VO_json, true_point_info_json, grid_info_json := h.Compress_all(vo_temp, truth_VO, true_point_info, grid_info)
	VO_queue, truth_VO, true_point_info, grid_info := h.Decompress_all(VO_queue_json, truth_VO_json, true_point_info_json, grid_info_json)
	err_truth := h.Verify(truth_VO, true_point_info, truthADS)
	if err_truth != nil {
		return err_truth
	}
	err_grid, bound_info := h.Verify_bound(query, &VO_queue, point_info, true_point_info, grid_info)
	if err_grid != nil {
		return err_grid
	}
	err := h.Rebuild(query, enterpoint, VO_queue, efSearch, ADS, true_point_info, bound_info)
	if err != nil {
		return err
	}
	return nil
}
